package csp;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;

import data.Bag;
import data.Binary;
import data.Constraint;
import data.FittingLimit;
import data.Item;
import data.MutualExclusive;

public class BacktrackSearch {

	//current csp being solved for
	private CSP csp;
	
	//A higher feature level uses the lower level features too (setting to FORWARD_CHECKING uses HEURISTIC)
	public static final int ALONE=0; //ALONE
	public static final int LOW=1; //HEURISTIC
	public static final int MEDIUM=2; //FORWARD CHECKING
	public static final int HIGH=3; //ARC CONSISTENCY
	private int featureLevel=0;
	
	public int consistencyChecks=0; //metric
	
	public boolean trace=false;
	
	public BacktrackSearch(HashMap<String, Item> variables, HashMap<String, Bag> values, FittingLimit fittingLimit)
	{
		csp = new CSP(variables, values, fittingLimit);
	}
	
	public BacktrackSearch(HashMap<String, Item> variables, HashMap<String, Bag> values, FittingLimit fittingLimit, int featureLevel)
	{
		this.featureLevel=featureLevel;
		csp = new CSP(variables, values, fittingLimit);
	}
	
	public void setFeatureLevel(int featureLevel)
	{
		this.featureLevel=featureLevel;
	}
	
	
	/**
	 * Call this to find a solution, if any
	 * @return Assignment list, if there is one
	 * @return null, otherwise
	 */
	public HashMap<Item, Bag> search() {
		return backtrack(new HashMap<Item, Bag>(), csp);
	}
	
	private HashMap<Item, Bag> backtrack(HashMap<Item, Bag> assignments, CSP csp) {
		if (assignments.size()==csp.Variables().size()) {
			trace("Done, assignments are full");
			return assignments;
		}
		if (!checkBagMinimumLimit(assignments, csp)) {
			trace("Bag minimum limit cant be met anymore. Backtracking.");
			return null;
		}
		
		Item var = selectVariable(assignments, csp); //apply selection heuristics
		
		trace("============");
		trace("Trying variable: " + var.Name);
		
		ArrayList<Bag> domain = var.Domain;
		orderDomain(domain, csp, assignments); //apply value ordering heuristics
		
		CSP newCsp = new CSP(csp); //copy csp data (so we can easily revert changes to domains)
		for (Bag value : domain) { //check values in the domain
			if (checkConsistency(csp, assignments, var, value)) { //check for consistency for the current value
				trace("	Trying consistent value assignment: " + var.Name + " / " + value.Name);
				assignments.put(var, value); //valid value

				newCsp = forwardCheck(newCsp, assignments, var);
				if (newCsp==null)
					return null;
				HashMap<Item, Bag> result = backtrack((HashMap<Item, Bag>)assignments.clone(), newCsp);
				if (result!=null)
					return result;
			} else {
				trace("	Invalid value assignment: " + var.Name + " / " + value.Name);
			}
		}
		
		trace("============");
		
		return null;
	}
	
	private CSP forwardCheck(CSP csp, HashMap<Item, Bag> assignments, Item last) {
		if (this.featureLevel>=this.MEDIUM) {
			csp.forwardCheck(assignments, last);
		}
		return csp;
	}

	private void trace(String s) {
		if (trace)
			System.out.println(s);
	}
	
	private Item selectVariable(HashMap<Item, Bag> assignments, CSP csp) {
		
		if (this.featureLevel>=BacktrackSearch.LOW) {
			//MRV
			int minVals=Integer.MAX_VALUE;
			ArrayList<Item> best=new ArrayList<Item>();
			for (Item var : csp.Variables()) {
				if (!assignments.containsKey(var)){
					if (var.Domain.size()<minVals) {
						best=new ArrayList<Item>();
						best.add(var);
					} else if (var.Domain.size()==minVals) {
						best.add(var);
					}
				}
			}
			//Degree among remaining items from the MRV
			HashMap<Item, Integer> unassigned = new HashMap<Item, Integer>();
			for (Item var : best) {
				if (!unassigned.containsKey(var))
					unassigned.put(var, new Integer(0));
				
				for (Binary bin : var.BinaryConstraints) {
					Item a = bin.VariableA;
					Item b = bin.VariableB;
					
					if (!unassigned.containsKey(a))
						unassigned.put(a, new Integer(1));
					else 
						unassigned.put(a, unassigned.get(a).intValue()+1);
					
					if (!unassigned.containsKey(b))
						unassigned.put(b, new Integer(1));
					else 
						unassigned.put(b, unassigned.get(b).intValue()+1);
				}
			}
			int val=Integer.MIN_VALUE;
			Item mostConstraints=null;
			for (Item var : unassigned.keySet()) {
				if (unassigned.get(var).intValue()>val) {
					val=unassigned.get(var).intValue();
					mostConstraints=var;
				}
			}
			
			return mostConstraints;
		} else {
			//return first unassigned variable
			for (Item var : csp.Variables()) {
				if (!assignments.containsKey(var))
				{
					return var;
				}
			}
		}
		
		return null;
	}
	
	private ArrayList<Bag> orderDomain(ArrayList<Bag> domain, CSP csp, HashMap<Item, Bag> assignments)
	{
		//LCV
		if (this.featureLevel>=BacktrackSearch.LOW) {
			
			ArrayList<Item> unassigned = new ArrayList<Item>();
			HashMap<Bag, Integer> bagCs = new HashMap<Bag, Integer>();
			for (Bag b : domain) {
				bagCs.put(b, new Integer(0));
			}
			for (Item var : csp.Variables()) {
				if (!assignments.containsKey(var))
					unassigned.add(var);
				
				for (MutualExclusive me : var.MutualExclusiveConstraints) {
					Bag b1 = me.ValueA;
					Bag b2 = me.ValueB;
					if (domain.contains(b1)) {
						bagCs.put(b1, bagCs.get(b1).intValue()+1);
					}
					if (domain.contains(b2)) {
						bagCs.put(b2, bagCs.get(b2).intValue()+1);
					}
				}
			}
			final HashMap<Bag, Integer> hack = bagCs;
			Collections.sort(domain, new Comparator(){
				@Override
				public int compare(Object o1, Object o2) {
					Bag b1=(Bag)o1;
					Bag b2=(Bag)o2;
					
					if (hack.get(b1).intValue()>hack.get(b2).intValue())
						return 1;
					else if (hack.get(b1).intValue()<hack.get(b2).intValue())
						return -1;
					return 0;
				}
			});
		} else {
			return domain;
		}
		
		return null;
	}
	
	private boolean checkConsistency(CSP csp, HashMap<Item, Bag> assignments, Item var, Bag value) {
		consistencyChecks++;
		
		for (Item item : csp.Variables()) {
			for (Constraint c : item.BinaryConstraints) {
				if (!c.IsSatisfied(assignments))
					return false;
			}
			for (Constraint c : item.MutualExclusiveConstraints) {
				if (!c.IsSatisfied(assignments))
					return false;
			}
			for (Constraint c : item.UnaryConstraints) {
				if (!c.IsSatisfied(assignments))
					return false;
			}
		}
		
		trace("\t\tConstraints ok");
		
		//Check bag weights and item capacity
		HashMap<Bag, Integer> contents = new HashMap<Bag, Integer>();
		HashMap<Bag, Integer> numItems = new HashMap<Bag, Integer>();
		for (Bag bag : csp.Values()) {
			contents.put(bag, new Integer(0));
			numItems.put(bag, new Integer(0));
		}
		for (Item key : assignments.keySet()) {
			Bag bag = assignments.get(key);
			int val = contents.get(bag).intValue();
			val+=key.Weight;
			if (val>bag.Capacity) {
				trace("\t\t Too much weight in bag: " + bag.Name);
				return false;
			}
			contents.put(bag, new Integer(val));
			
			int num = numItems.get(bag).intValue();
			num++;
			if ((csp.fittingLimit!=null)&&(num>csp.fittingLimit.UpperBound)) {
				trace("\t\t Too many items in bag: " + bag.Name);
				return false;
			}
			numItems.put(bag, new Integer(num));
		}

		return true;
	}
	
	private boolean checkBagMinimumLimit(HashMap<Item, Bag> assignments, CSP csp) {
		//check if items left < num items required to fill bag minimums
		if (csp.fittingLimit==null) return true;
		
		int itemsLeft = csp.Variables().size() - assignments.keySet().size();
		int itemsNeeded = csp.Values().size()*csp.fittingLimit.LowerBound;
		
		HashMap<Bag, Integer> numItems = new HashMap<Bag, Integer>();
		for (Bag bag : csp.Values()) {
			numItems.put(bag, new Integer(0));
		}
		for (Item key : assignments.keySet()) {
			Bag bag = assignments.get(key);
			int num = numItems.get(bag).intValue();
			num++;
			
			if (num<=csp.fittingLimit.LowerBound)
				itemsNeeded--;
			
			numItems.put(bag, new Integer(num));
		}
		
		if (itemsNeeded>itemsLeft) {
			return false;
		}
		
		return true;
	}
	
	public static void printSolution(HashMap<Item, Bag> soln, int consistencyChecks) {
		if (soln==null) {
			System.out.println("null");
			return;
		}
		
		System.out.println("Done in " + consistencyChecks + " consistency checks.");
		for (Item key : soln.keySet()) {
			System.out.println(key.Name + " in " + soln.get(key).Name);
		}
	}
	
}
